package hard.区间问题.跳跃游戏;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 跳跃游戏
 * @date 2022/11/20 15:06
 */
public class Demo55 {
    public static void main(String[] args) {
        int[] ints={3,2,1,0,4};
        boolean b = canJump(ints);
        System.out.println(b);
    }
    public static boolean canJump(int[] nums) {
        int length1 = nums.length;
        if(length1 ==1){
            return true;
        }

        //这里从倒数第二个开始遍历更好，因为最后一个数可以为0;
        for (int length = length1 -1; length >=0; length--) {
            if(nums[length]==0){
                int index=length-1;
                while (index>=0){
                    if(index+nums[index]>length){
                        length=index;
                        break;
                    //这里其实就是判断最后一个数为0的情况，如果从倒数第二个数开始遍历，此处可以省略
                    } else if(index+nums[index]==length1 -1){
                        length=index;
                        break;
                    }else {
                        index--;
                    }
                }
                if(index<0){
                    return false;
                }
            }
        }
        return true;
    }
    //优化
    public static boolean canJump2(int[] nums) {
        int length1 = nums.length;
        if(length1 ==1){
            return true;
        }

        //这里从倒数第二个开始遍历更好，因为最后一个数可以为0;
        for (int length = length1 -2; length >=0; length--) {
            if(nums[length]==0){
                int index=length-1;
                while (index>=0){
                    if(index+nums[index]>length){
                        length=index;
                        break;
                        //这里其实就是判断最后一个数为0的情况，如果从倒数第二个数开始遍历，此处可以省略
                    }else {
                        index--;
                    }
                }
                if(index<0){
                    return false;
                }
            }
        }
        return true;
    }
}
